package xyf.p02.stack_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * ClassName: J059_QueueMax
 * Description:
 * Author: xyf
 * Date: 9/7/22 7:49 PM
 * Version: 1.0
 **/
public class J059_WindowMax
{
    public int[] maxSlidingWindow(int[] nums, int k)
    {
        int[] res = new int[nums.length - k + 1];

        Deque<Integer> deque = new LinkedList<>();


        for (int i = 0; i < k; i++)
        {
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        res[0] = nums[deque.peekFirst()];

        for (int i = k; i < nums.length; i++)
        {
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            {
                deque.pollLast();
            }
            deque.offerLast(i);
            if (!deque.isEmpty() && deque.peekFirst() == i - k)
            {
                deque.pollFirst();
            }

            res[i - k + 1] = nums[deque.peekFirst()];
        }
        return res;
    }
}